#include <iostream>
#include <vector>

using namespace std;

// https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/description/?envType=daily-question&envId=2025-06-09
// 440. 字典序的第K小数字

class Solution1 {
public:
    int findKthNumber(int n, int k) {
        int curNum = 1;
        for (int i = 0; i < n && k > 1; i++, --k)
        {
            if(curNum * 10 <= n){
                curNum *= 10;
            }else{
                while(curNum >= n || (curNum + 1) % 10 == 0){
                    curNum /= 10;
                }
                ++curNum;
            }
        }
        return curNum;
    }
};

class Solution {
public:
    int countNodeSize(int node ,int n, int k){
        long long left = node;
        long long right = node + 1;
        long long size = 0;
        while (left <= n)
        {
            size += min(n + 1LL, right) - left;
            left *= 10;
            right *= 10;
        }
        return size;
    }
    int findKthNumber(int n, int k) {
        int ans = 1;
        k--;
        while(k > 0){
            int curSize = countNodeSize(ans, n, k);
            if(curSize <= k){
                k -= curSize;
                ans += 1;
            }else{
                ans *= 10;
                k--;
            }
        }
        return ans;
    }
};

int main()
{
    return 0;
}